def coin_change(coins, amount):
    """
    硬币找零问题 - 最小硬币数
    coins: 硬币面额列表
    amount: 目标金额
    """
    # dp[i] 表示凑出金额i所需的最少硬币数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 金额0需要0个硬币
    
    # 记录硬币选择，用于回溯
    coin_used = [-1] * (amount + 1)
    
    for i in range(1, amount + 1):
        for coin in coins:
            if i >= coin and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                coin_used[i] = coin
    
    if dp[amount] == float('inf'):
        return -1, []  # 无法凑出金额
    
    # 回溯找出使用的硬币
    result = []
    current = amount
    while current > 0:
        coin = coin_used[current]
        result.append(coin)
        current -= coin
    
    return dp[amount], result

# 测试
coins = [1, 2, 5]
amount = 11
min_coins, coin_list = coin_change(coins, amount)

print(f"\n硬币找零问题：")
print(f"硬币面额: {coins}")
print(f"目标金额: {amount}")
print(f"最少硬币数: {min_coins}")
print(f"硬币组合: {coin_list}")

# 另一个测试
coins = [2]
amount = 3
min_coins, coin_list = coin_change(coins, amount)
print(f"\n硬币面额: {coins}")
print(f"目标金额: {amount}")
print(f"最少硬币数: {min_coins}")
print(f"硬币组合: {coin_list}")